import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/*
 * @lc app=leetcode.cn id=47 lang=java
 *
 * [47] 全排列 II
 *
 * https://leetcode-cn.com/problems/permutations-ii/description/
 *
 * algorithms
 * Medium (56.05%)
 * Likes:    195
 * Dislikes: 0
 * Total Accepted:    33.1K
 * Total Submissions: 58.7K
 * Testcase Example:  '[1,1,2]'
 *
 * 给定一个可包含重复数字的序列，返回所有不重复的全排列。
 *
 * 示例:
 *
 * 输入: [1,1,2]
 * 输出:
 * [
 * ⁠ [1,1,2],
 * ⁠ [1,2,1],
 * ⁠ [2,1,1]
 * ]
 *
 */

// @lc code=start
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    boolean[] dp;
    public List<List<Integer>> permuteUnique(int[] nums) {
        dp = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(0, nums);
        return this.res;
    }

    void dfs(int n, int[] nums) {
        if(n == dp.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0; i < nums.length; i++){
            if(!dp[i]) {
                //dp[i-1] 也能通过，但是剪枝不彻底，因为对于重复的元素，只取第一个
                if(i>0&&nums[i]==nums[i-1]&&!dp[i-1])
                {
                    continue;
                }
                dp[i] = true;
                this.list.add(nums[i]);
                dfs(n+1, nums);
                this.list.remove(list.size()-1);
                dp[i] = false;
            }
        }
    }
}
// @lc code=end

